package Competition;

import org.junit.Test;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Competition
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-29  09:19
 * @Description: TODO
 * @Version: 1.0
 */
public class 元素和最小的山形三元组2908 {

    // 采用的暴力的方法
    public int minimumSum(int[] nums) {
        int res = -1;
        for (int i = 1; i < nums.length; i++) {
            int left = 0, right = nums.length - 1;
            int minL = nums[left], minR = nums[right];
            while (left < i) {
                if (nums[left] < minL) {
                    minL = nums[left];
                }
                left++;
            }
            while (right > i) {
                if (nums[right] < minR) {
                    minR = nums[right];
                }
                right--;
            }
            if (minL < nums[i] && minR < nums[i]) {
                int sum = minL  + nums[i] + minR;
                if (res == -1) {
                    res = sum;
                } else if (sum < res) {
                    res = sum;
                }
            }
        }
        return res;
    }

    public int minimumSum2(int[] nums) {
        int n = nums.length;
        int[] suf = new int[n];
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i > 1; i--) {
            suf[i] = Math.min(suf[i + 1], nums[i]);
        }
        int ans = Integer.MAX_VALUE;
        int pre = nums[0];
        for (int j = 1; j < n - 1; j++) {
            if (pre < nums[j] && nums[j] > suf[j + 1]) {
                ans = Math.min(ans, pre + nums[j] + suf[j + 1]);
            }
            pre = Math.min(pre, nums[j]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    @Test
    public void test(){
        int i = minimumSum2(new int[]{8,6,1,5,3});
        System.out.println(i);
    }
}
